import java.awt.event.MouseAdapter;
import java.util.*;

public class project {
    public String kthLargestNumber(String[] nums, int k) {
        PriorityQueue<String> queue=new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.length()<o2.length()){
                    return -1;
                }else if(o2.length()<o1.length()){
                    return 1;
                }else{
                    return o1.compareTo(o2);
                }
            }
        });
        for(String str : nums){
            queue.offer(str);
            if(queue.size()>k){
                queue.poll();
            }
        }
        return queue.peek();
    }












    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue=new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1)-(o1.get(0)+o1.get(1)));
            }
        });
        for(int i=0;i<Math.min(nums1.length,k);i++){
            for(int j=0;j<Math.min(nums2.length,k);j++){
                if(queue.size()<k){
                    List<Integer> list=new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    queue.add(list);
                }else{
                    int tmp=queue.peek().get(0)+queue.peek().get(1);
                    if(tmp>nums1[i]+nums2[j]){
                        queue.poll();
                        List<Integer> list=new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        queue.add(list);
                    }
                }
            }
        }
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<k&&!queue.isEmpty();i++){
            list.add(queue.poll());
        }
        return list;
    }












    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int val=entry.getValue();
            int key=entry.getKey();
            if(queue.size()<k){
                queue.add(new int[]{key,val});
            }else{
                if(queue.peek()[1]<val){
                    queue.poll();
                    queue.add(new int[]{key,val});
                }
            }
        }
        int[] arr=new int[k];
        for(int i=0;i<k;i++){
            arr[i]=queue.poll()[0];
        }
        return arr;
    }









    public int kthSmallest(int[][] matrix, int k) {
        int row=matrix.length;
        PriorityQueue<Integer> queue=new PriorityQueue<>((o1,o2)->o2-o1);
        for(int i=0;i<row;i++){
            int[] arr=matrix[i];
            for(int j=0;j<arr.length;j++){
                queue.add(arr[j]);
                if(queue.size()>k){
                    queue.poll();
                }
            }
        }
        return queue.peek();
    }








    public int nthUglyNumber(int n) {
        int[] arr=new int[]{2,3,5};
        Set<Long> set=new HashSet<>();
        PriorityQueue<Long> queue=new PriorityQueue<>();
        set.add(1l);
        queue.add(1l);
        int sum=0;
        for(int i=0;i<n;i++){
            long cur=queue.poll();
            sum=(int)cur;
            for(int a : arr){
                long next=a*cur;
                if(set.add(next)){
                    queue.offer(next);
                }

            }
        }
        return sum;
    }















    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]-o2[1];
            }
        });
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int key=entry.getKey();
            int val=entry.getValue();
            if(queue.size()==k){
                if(queue.peek()[1]<val){
                    queue.poll();
                    queue.offer(new int[]{key,val});
                }
            }else{
                queue.offer(new int[]{key,val});
            }
        }
        int[] arr=new int[k];
        for(int i=0;i<k;i++){
            arr[i]=queue.poll()[0];
        }
        return arr;
    }










    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int i=0;i<nums.length;i++){
            if(i<k){
                queue.offer(nums[i]);
            }else{
                if(queue.peek()<nums[i]){
                    queue.poll();
                    queue.add(nums[i]);
                }
            }
        }
        return queue.peek();
    }








    public String frequencySort(String s) {
        if(s.length()<2){
            return s;
        }
        int[] arr=new int[128];
        char[] ch=s.toCharArray();
        for(int i=0;i<ch.length;i++){
            arr[ch[i]]++;
        }

        PriorityQueue<Character> queue=new PriorityQueue<>(new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                return arr[o2]-arr[o1];
            }
        });
        for(int i=0;i<128;i++){
            if(arr[i]!=0){
                queue.add((char)i);
            }
        }
        StringBuilder sb=new StringBuilder();
        while(!queue.isEmpty()){
            char c=queue.poll();
            while(arr[c]>0){
                sb.append(c);
                arr[c]--;
            }
        }
        return sb.toString();
    }








    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int i=0;i<nums.length;i++){
            if(i<k){
                queue.offer(nums[i]);
            }else{
                if(queue.peek()<nums[i]){
                    queue.poll();
                    queue.add(nums[i]);
                }
            }
        }
        return queue.peek();
    }










    public int[] minOperations(String boxes) {
        int[] arr=new int[boxes.length()];
        int left=0;
        int right=0;
        int count=0;
        left=boxes.charAt(0)=='1'?1:0;
        for(int i=1;i<boxes.length();i++){
            if(boxes.charAt(i)=='1'){
                right++;
                count+=i;
            }
        }
        arr[0]=count;
        for(int i=1;i<boxes.length();i++){
            count=count+left-right;
            if(boxes.charAt(i)=='1'){
                left++;
                right--;
            }
            arr[i]=count;
        }
        return arr;
    }
}
